package com.dylan.历史.算法.排序;

import com.dylan.历史.util.LogUtil;

import java.util.Arrays;

/**
 * Created by Dylan on 2018/10/23.
 */
public class 基础_排序_归并排序 {

    public static void main(String[] args) {
        LogUtil.info(Arrays.toString(mergeSort(new int[]{3, 6, 2, 7, 2, 6, 8, 0})));
    }

    static int[] mergeSort(int[] arr) {
        int len = arr.length;
        int[] arr1 = new int[len];
        mergeSort(arr, 0, len - 1, arr1);
        return arr1;
    }

    /**
     * 归并排序算法 O(nlogn)
     * 先将初始的序列表看成是n个长度为1的有序表，然后进行归并
     * 先将数组分为左右两部分，使左右两部分在arr2中分别有序
     * 然后将arr2的有序部分合并到arr1
     * 归并排序借助多余的空间，来避免数组中的数据交换
     */
    static void mergeSort(int[] arr, int s, int t, int[] arr1) {
        if (s == t) {
            arr1[s] = arr[s];
            return;
        }
        int[] arr2 = new int[arr.length];
        int m = (s + t) / 2;
        mergeSort(arr, s, m, arr2);
        mergeSort(arr, m + 1, t, arr2);
        merge(arr2, s, m, t, arr1);
    }

    static void merge(int[] arr, int s, int m, int t, int[] arr1) {
        int i = s;
        int j = m + 1;
        int k = s;
        while (i <= m && j <= t) {
            if (arr[i] <= arr[j]) {
                arr1[k++] = arr[i++];
            } else {
                arr1[k++] = arr[j++];
            }
        }
        while (i <= m) {
            arr1[k++] = arr[i++];
        }
        while (j <= t) {
            arr1[k++] = arr[j++];
        }
    }
}
